Data flow graphs include a plurality of nodes that define how a query is to be executed. Such data flow graphs are sometimes optimized using rules to determining how to change the data flow graph. If the data flow graph is more complex and several rules can be applied, rule-based optimization techniques often apply the wrong rules and/or the rules are applied in an incorrect order. Such instances can occur when one rule changes the preconditions for another rule so that the rule cannot be applied anymore. These cases as well as other situations in which there are conflicting rules typically results in sub-optimal query execution plans.